Tjoi2016&Heoi2016 字符串

发表于
字数统计: 1,284字 | 阅读时长 ≈ 7min

Tjoi2016&Heoi2016 字符串

问题描述

佳媛姐姐过生日的时候，她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了一个长为n的字符串s，和m个问题。佳媛姐姐必须正确回答这m个问题，才能打开箱子拿到礼物，升职加薪，出任CEO，嫁给高富帅，走上人生巅峰。每个问题均有a,b,c,d四个参数，问你子串s[a..b]的所有子串和s[c..d]的最长公共前缀的长度的最大值是多少？佳媛姐姐并不擅长做这样的问题，所以她向你求助，你该如何帮助她呢？

输入格式

输入的第一行有两个正整数n,m，分别表示字符串的长度和询问的个数。接下来一行是一个长为n的字符串。接下来m行，每行有4个数a,b,c,d，表示询问s[a..b]的所有子串和s[c..d]的最长公共前缀的最大值。

输出格式

对于每一次询问，输出答案。

样例输入

5 5
aaaaa
1 1 1 5
1 5 1 1
2 3 2 3
2 4 2 3
2 3 2 4

样例输出

1
1
2
2
2

提示

1<=n,m<=100,000,字符串中仅有小写英文字母，a<=b,c<=d,1<=a,b,c,d<=n

首先，后缀自动机上处理公共前缀问题都是将原串倒过来建立后缀自动机。

倒过来处理之后，$a’=n-b+1,b’=n-a+1,c’=n-d+1,d’=n-c+1$问题转换为询问s’[a’…b’]的所有子串与s’[c’…d’]的最长公共后缀的最大值。

直接找并不好找，考虑二分答案，将最优化问题转为判定性问题。

假设答案是$mid$，问题就转换为了判断s’[d’-mid+1,d’]是否为s’[a’…b’]的子串。那么只需要判断s’[d’-mid+1,d’]的right集合中是否含有[a’+mid-1,b’]中的位置即可。

找到s’[d’-mid+1,d’]的对应位置用倍增，维护right集合采用线段树合并。时间复杂度$O(nlog^2n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<vector>
#define MAXN 400005
#define MAXT 10000005
using namespace std;

int N,M,pos[MAXN];
char s[MAXN];

namespace Seg{
	int tot,rt[MAXN],ls[MAXT],rs[MAXT],cnt[MAXT];
	
	void Update(int p){cnt[p]=cnt[ls[p]]+cnt[rs[p]];}
	
	void Modify(int &p,int k,int l,int r){
		if(!p)p=++tot;
		if(l==r){cnt[p]++;return;}
		int mid=l+r>>1;
		if(k<=mid)Modify(ls[p],k,l,mid);
		else Modify(rs[p],k,mid+1,r);
		Update(p);
	}
	
	int Merge(int x,int y,int l,int r){
		if(!x||!y)return x|y;
		int p=++tot;
		if(l==r){cnt[p]=cnt[x]+cnt[y];return p;}
		int mid=l+r>>1;
		ls[p]=Merge(ls[x],ls[y],l,mid);
		rs[p]=Merge(rs[x],rs[y],mid+1,r);
		Update(p);
		return p;
	}
	
	int Query(int p,int x,int y,int l,int r){
		if(!p)return 0;
		if(x<=l&&r<=y)return cnt[p];
		int mid=l+r>>1,ret=0;
		if(x<=mid)ret+=Query(ls[p],x,y,l,mid);
		if(y>mid)ret+=Query(rs[p],x,y,mid+1,r);
		return ret;
	}
}

namespace SAM{
	int rt,tot,las,mx[MAXN],par[MAXN][19],son[MAXN][26];
	vector<int>G[MAXN];
	
	int push(int val){mx[++tot]=val;return tot;}
	
	void init(){tot=0;rt=las=push(0);}
	
	void ins(int t){
		int p,q,np,nq;
		np=push(mx[las]+1);
		for(p=las;p&&(!son[p][t]);p=par[p][0])son[p][t]=np;
		if(!p)par[np][0]=rt;
		else{
			q=son[p][t];
			if(mx[q]==mx[p]+1)par[np][0]=q;
			else{
				nq=push(mx[p]+1);
				memcpy(son[nq],son[q],sizeof(son[q]));
				par[nq][0]=par[q][0];
				par[q][0]=par[np][0]=nq;
				for(;p&&son[p][t]==q;p=par[p][0])son[p][t]=nq;
			}
		}
		las=np;
	}
	
	void build(){for(int i=2;i<=tot;i++)G[par[i][0]].push_back(i);}
	
	void dfs(int x){
		int i,y;
		for(i=1;i<19;i++)par[x][i]=par[par[x][i-1]][i-1];
		for(i=0;i<G[x].size();i++){
			y=G[x][i];dfs(y);
			Seg::rt[x]=Seg::Merge(Seg::rt[x],Seg::rt[y],1,N);
		}
	}
	
	int jump(int p,int d){
		for(int i=18;i>=0;i--)if(mx[par[p][i]]>=d)p=par[p][i];
		return p;
	}
}

void solve(int a,int b,int c,int d){
	int l=1,r=min(b-a+1,d-c+1),mid,p;
	while(l<=r){
		mid=l+r>>1;
		p=SAM::jump(pos[d],mid);
		if(Seg::Query(Seg::rt[p],a+mid-1,b,1,N))l=mid+1;
		else r=mid-1;
	}
	printf("%d\n",r);
}

int main(){
	int i,l,r,a,b,c,d;
	scanf("%d%d%s",&N,&M,s+1);
	for(i=1;i<N-i+1;i++)swap(s[i],s[N-i+1]);
	
	SAM::init();
	for(i=1;i<=N;i++){
		SAM::ins(s[i]-'a');
		pos[i]=SAM::las;
	}
	for(i=1;i<=N;i++)Seg::Modify(Seg::rt[pos[i]],i,1,N);
	SAM::build();
	SAM::dfs(SAM::rt);
	
	for(i=1;i<=M;i++){
		scanf("%d%d%d%d",&a,&b,&c,&d);
		a=N-a+1;b=N-b+1;c=N-c+1;d=N-d+1;
		swap(a,b);swap(c,d);
		solve(a,b,c,d);
	}
}